/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
class Solution {
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
    	vector<vector<int>> output;
    	if(!pRoot)
    		return  output;
    	s1.push(pRoot);
        while(!s1.empty() || !s2.empty())
        {
        	vector<int> line1;
        	while(!s1.empty())
        	{
        		TreeNode * top = s1.top();
        		s1.pop();
        		line1.push_back(top->val);
        		if(top->left)
        			s2.push(top->left);
        		if(top->right)
        			s2.push(top->right);
        	}
        	if(!line1.empty())
        		output.push_back(line1);
        	vector<int> line2;
        	while(!s2.empty())
        	{
        		TreeNode *top = s2.top();
        		s2.pop();
        		line2.push_back(top->val);
        		if(top->right)
        			s1.push(top->right);
        		if(top->left)
        			s1.push(top->left);
        	}
        	if(!line2.empty())
        		output.push_back(line2);
        }
        return output;
    }
private:
	stack<TreeNode *> s1,s2;
};